package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/6/14 16:00
 */
public class C63 {

    public static int uniquePathWithObstacles(int[][] obstacleGrid) {
        return process(obstacleGrid, 0, 0);
    }

    // 向右向下到终点, 不能走障碍网格
    public static int process(int[][] grid, int i, int j) {
        if (i == grid.length || j == grid[0].length || grid[i][j] == 1)
            return 0;
        if (i == grid.length - 1 && j == grid[0].length - 1)
            return 1;
        int ways = process(grid, i + 1, j);
        ways += process(grid, i, j + 1);
        return ways;
    }

    public static int dp(int[][] obstacleGrid) {
        int M = obstacleGrid.length, N = obstacleGrid[0].length;
        if(obstacleGrid[M-1][N-1] == 1) return 0;
        int[][] dp = new int[M][N];
        dp[M - 1][N - 1] = 1;
        for (int c = N - 2; c >= 0; c--) {
            dp[M - 1][c] = obstacleGrid[M - 1][c] == 1 ? 0 : dp[M - 1][c + 1];
        }
        for (int r = M - 2; r >= 0; r--) {
            dp[r][N - 1] = obstacleGrid[r][N - 1] == 1 ? 0 : dp[r + 1][N - 1];
        }

        for (int i = M - 2; i >= 0; i--) {
            for (int j = N - 2; j >= 0; j--) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }

    // for test
    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 0}, {0, 1, 0}, {0, 0, 0}
        };
        System.out.println(uniquePathWithObstacles(grid));
    }

}
